package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/design-hashset/">设计哈希集合(Design HashSet)</a>
 * <p>不使用任何内建的哈希表库设计一个哈希集合（HashSet）。</p>
 * <p>
 * 实现 MyHashSet 类：
 *      <ul>
 *          <li>void add(key) 向哈希集合中插入值 key 。</li>
 *          <li>bool contains(key) 返回哈希集合中是否存在这个值 key 。</li>
 *          <li>void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。</li>
 *      </ul>
 * </p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例：
 *      输入：
 *          ["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
 *          [[], [1], [2], [1], [3], [2], [2], [2], [2]]
 *      输出：
 *          [null, null, null, true, false, null, true, null, false]
 *      解释：
 *          MyHashSet myHashSet = new MyHashSet();
 *          myHashSet.add(1);      // set = [1]
 *          myHashSet.add(2);      // set = [1, 2]
 *          myHashSet.contains(1); // 返回 True
 *          myHashSet.contains(3); // 返回 False ，（未找到）
 *          myHashSet.add(2);      // set = [1, 2]
 *          myHashSet.contains(2); // 返回 True
 *          myHashSet.remove(2);   // set = [1]
 *          myHashSet.contains(2); // 返回 False ，（已移除）
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <li>0 <= key <= 10^6</li>
 * <li>最多调用 10^4 次 add、remove 和 contains</li>
 * </p>
 *
 * @author c2b
 * @see LC0705DesignHashSet_S 设计哈希集合(Design HashSet)
 * @see LC0706DesignHashMap_S 设计哈希映射(Design HashMap)
 * @see LC707DesignLinkedList_M 设计链表(Design Linked List)
 * @see LC1206DesignSkiplist_H 设计跳表(Design Skiplist)
 * @since 2023/5/10 9:09
 */
public class LC0705DesignHashSet_S {

    static class MyHashSet {
        /*
            由于题目给出了 0 <= key <= 10^6 数据范围，同时限定了 key 只能是 int。
            直接使用一个 boolean 数组记录某个 key 是否存在，key 直接对应 boolean 的下标。
         */
        //boolean[] valArr = new boolean[1000001];
        //
        //public MyHashSet() {
        //
        //}
        //
        //public void add(int key) {
        //    valArr[key] = true;
        //}
        //
        //public void remove(int key) {
        //    valArr[key] = false;
        //}
        //
        //public boolean contains(int key) {
        //    return valArr[key];
        //}


        /*
            分桶数组：类似于bitmap的数据结构。
            使用int的每一bit位的0，1表示一个数字是否存在
            因此我们可以建立一个 buckets 数组，数组装载的 int 类型数值。
                先对 key 进行 key / 32，确定当前 key 所在桶的位置（大概位置）
                再对 key 进行 1<<(key % 32)，确定当前 key 所在桶中的哪一位（精确位置）
            根据位运算对「精确位置」进行修改。
         */

        // 1000001：最大数量量。int类型：32位。1000001/32=31250.03125，向上取整：31251
        int[] valArr = new int[31251];

        public MyHashSet() {

        }

        public void add(int key) {
            // key / 32：得到数组中的数
            // bit：对应的比特位
            int bucketIndex = key / 32;
            long bitIndex = 1L << (key % 32);
            valArr[bucketIndex] |= (1 << bitIndex);
        }

        public void remove(int key) {
            int bucketIndex = key / 32;
            long bitIndex = 1L << (key % 32);
            valArr[bucketIndex] &= ~(1 << bitIndex);
        }

        public boolean contains(int key) {
            int bucketIndex = key / 32;
            long bitIndex = 1L << (key % 32);
            return (valArr[bucketIndex] & (1 << bitIndex)) != 0;
        }
    }

    public static void main(String[] args) {
        MyHashSet myHashSet = new MyHashSet();
        myHashSet.add(1);
        myHashSet.add(2);
        System.out.println(myHashSet.contains(1));  // true
        System.out.println(myHashSet.contains(3));  // false
        myHashSet.add(2);
        System.out.println(myHashSet.contains(2));  // true
        myHashSet.remove(2);
        System.out.println(myHashSet.contains(2));  // false
    }
}